#include <stdio.h>
#include <cassert>

// This class manages available ID use a single linked list, which is implemnent by an array
// We simply use an integer array to save half space as we could resue the "value" feild & the "next" feild:
// 1. The value type is of the same type of index
// 2. The value's range is the same as index
// 

const static char LIST_END = -1;

template <typename integer>
class idallocator
{
public:
	idallocator(integer _num): num(_num)
	{
		array = new integer[num];

		// Initialize the linked list. Initially, it is a full linked list with all elements linked one after another.
		head = 0;
		for (integer i = 0; i < num; i++)
		{
			array[i] = i + 1;
		}
		array[num-1] = LIST_END;

		count = num;
	}

	~idallocator()
	{
		delete [] array;
	}



	integer allocate() // pop_front, remove a node from the front
	{
		int id = head;
		if(id != LIST_END)
		{
			head = array[head];
			count--;
		}
		return id;
	}

	// push_front, add a new node to the front
	void free(const integer& id) 
	{
		array[id] = head;
		count++;
		head = id;
	}

	// push_front, add a new node to the front
	bool free_s(const integer& id) 
	{
		// make sure this id is not in the list before we add it
		if(exist(id)) return false; 
		free(id);
		return true;
	}

	size_t size() const
	{
		return count;
	}

private:
	bool exist(const integer& id)
	{
		int i = head;
		while (i != LIST_END)
		{
			if(i == id) return true;
			i = array[i];
		}

		return false;
	}

private:
	integer* array;
	integer num;		// totall number of the array
	integer count;		// number in the linked list
	int head;		// index of the head of the linked list

};


// Use array to implement double linked list
// TODO:
// 1. Implement iterator
// 2. Don't use idallocator to save memory
template <class DataType>
class arraylist
{
	struct node
	{
		DataType data;
		int previous;
		int next;
	};

public:
	arraylist(int _num): num(_num), idor(*(new idallocator<int>(_num)))
	{
		array = new node[num];
		head = LIST_END;
		tail = LIST_END;
	}

	~arraylist()
	{
		delete [] array;
		delete &idor;
	}

	bool push_front(const DataType& data)
	{
		int id = idor.allocate();
		if(id == LIST_END) return false;

		array[id].data = data;
		array[id].next = head;	
		array[id].previous = LIST_END;

		if(head != LIST_END) array[head].previous = id;	
		else tail = id;

		head = id;

		return true;
	}

	DataType pop_front()
	{
		if(head == LIST_END) return DataType();
		int id = head;
		head = array[head].next;
		array[head].previous = LIST_END;

		idor.free_s(id);

		return array[id].data;
	}

	bool push_back(const DataType& data)
	{
		int id = idor.allocate();
		if(id == LIST_END) return false;

		array[id].data = data;
		array[id].previous = tail;
		array[id].next = LIST_END;

		if(tail != LIST_END) array[tail].next = id;
		else head = id;

		tail = id;

		return true;
	}

	DataType pop_back()
	{
		if(tail == LIST_END) return DataType();
		int id = tail;
		tail = array[tail].previous;
		array[tail].next = LIST_END;

		idor.free_s(id);

		return array[id].data;
	}

	// position must be valid.
	bool insert(int position, const DataType& data)
	{
		// better check position first;

		int id1 = position;
		int id2 = idor.allocate();
		int id3 = array[id1].next;

		array[id1].next = id2;
		array[id2].previous = id1;
		array[id2].next = id3;
		array[id2].data = data;
		if(id3 != LIST_END) array[id3].previous = id2;
		else tail = id2;

		return true;

	}

	// position must be valid.
	DataType erase(int position)
	{
		// better check position first;

		int id1 = array[position].previous;
		int id2 = array[position].next;

		if(id1 != LIST_END) array[id1].next = id2;
		else head = id2;
		if(id2 != LIST_END) array[id2].previous = id1;
		else tail = id1;

		idor.free(position);

		return array[position].data;
	}

	bool empty()
	{
		return head == LIST_END;
	}

	size_t size()
	{
		return num - idor.size();
	}

	void print()
	{
		printf("count = %d ", this->size());
		int i = head;
		while (i != LIST_END)
		{
			printf("%d\t", array[i].data);
			i = array[i].next;
		}
		printf("\n");
	}

private:
	node* array;
	int num;
	int head;
	int tail;

	idallocator<int>&  idor;

};

int main()
{
	arraylist<int> by(12);
	by.push_front(1);
	by.push_front(2);
	by.push_front(3);
	by.push_front(4);
	by.push_front(5);
	by.push_front(6);
	by.push_front(7);

	by.print();

	by.erase(3);
	by.print();


	by.pop_back();
	by.print();

	by.pop_front();
	by.print();

	by.insert(5, 10);
	by.print();

	return 0;
}

